It will be convenient to discuss as background XML documents and known XML query techniques, but it will be appreciated that the invention is broader than that and applies to storing and querying data representative of documents generally.
At present an XML document, for example an address list with 1000 individuals and their addresses on it, is received by a user's computer and parsed by an XML reader. This stores an internal memory representation, or map, of the XML document in a memory of the computer. This is often termed the “Document Tree” and identifies nodes of the document.
To search for a specified node requires “walking the tree”, which involves comparing each node of the tree with a target node and looking for a match. This can be quick if by luck the target node is near the start of the tree, but if it is the 1000th node the comparison process has to go through 999 comparisons before it finds it. This can be a time consuming activity.
XPath expressions are used to query XML documents. They can specify a node or a plurality of nodes that contain target nodes, and walk the tree, as discussed above.
An XPath query to retrieve a particular node or nodes is of the kind:    A[m]/B[n]/C[o]/ . . . Z[y].
A is a root node (or perhaps context node—see later), and B is a child node of node A, and C is a child node of node B etc; and where m, n, o etc are ordinal integers indicating which ordinal of the node A, B, C etc is to be the child node taken in the pathway from the root node A to the final node Z[y]. The XPath query expression A[m]/B[n]/C[o] . . . effectively gives instructions to the parser to navigate the Document Tree from a start node to an end node or nodes to be retrieved.
It will be helpful to include at this point a brief discussion of terms used in XML and its structure.
An XML formatted data file contains a mixture of markup language and content. The markup provides a logical structure to the content and may also optionally have semantic meaning that a machine can be programmed to deal with.
Because the markup and content (text) are mixed, it is necessary to use some syntax to delimit the markup from the content. XML uses the characters ‘<’ and ‘>’ to separate a string of characters from the content. So the text “<root>” is a piece of markup language. The XML specification requires that the content and other markup following <root> is enclosed by an end tag as follows </root>. The <root> is referred to as a start tag and the two tags, together with the enclosed content, is a node called ELEMENT. Somewhat more loosely the nodes <root> and </root> are called the start element and the end element.
Nodes that are elements can contain other elements and content. Elements can also include ATTRIBUTES. An attribute can be considered to be defined inside a start tag and consists of a name followed by the ‘=’ followed by the attribute value which is within a double quoted string. For example in the XML expression: <root id=“123”></root>, id is an attribute, it's name is id, and it's value is 123.
XML parsers that parse an XML data file into computer memory generally store the XML document as a tree structure which is a familiar structure used in computer science. They also use the term NODE. A start and end tag denote a node. An attribute is a node, and the text content contained within a start and end tag is considered to be included in a TEXT node. Other types of node which could be encountered include processing instructions and CDATA sections.
For the XML below    <root id=“123”>hello</root>there are three nodes. The ‘root’ is a node (of type element), ‘id’ is a node (of type attribute), and hello is inside a node (of type TEXT).
The node representing the ‘root’ has the name root. The node representing ‘id’ has the name id. For XML there is no node name associated with the text node, although for the purposes of this patent all text nodes will have the default name text. A text node cannot contain any other nodes. Thus it must be a leaf node of the document tree.
The primary purpose of XPath is to provide a language for addressing parts of an XML language. The specification for XML is widely available, for example it is available from the W3C site http://www.w3.org. In this patent the expression XPath query is used to denote that the specification of an XPath is tantamount to querying an XML document.
In general an XPath expression can evaluate to a node, a set of nodes (unordered), a string (a sequences of characters), a boolean (true or false) or a number (floating point).
Many common XPath queries of practical importance are of the form                A[expression]/B[expression]/C/[expression] . . .where A, B and C are element names and the expression is defined by a grammar. Note this is not a definition, but a common pattern. An expression can be of the form, for example, of position( )>2 where position is a known function. The expression can also be just a single integer. Another example of an XPath query illustrating the use of expressions more fully is        document/subsection[@type=“important”]which returns all the “subsection” elements inside the “document” element which have an attribute with name “type” and value “important”. The expression in this case is @type=“important”. Because the document is not followed by square brackets it is assumed to mean [1], i.e. the first element.        
As previously discussed, XPath queries may take the form A[m]/B[n]/C[o] where A, B and C are tag names and m, n and o are ordinal (integers). The meaning of the expression is as follows. The separator character ‘/’ denotes that the element to the left is the parent of the element to the right. The integer value inside the square brackets e.g. A [m] specifies the mth occurrence of the element A amongst its siblings (nodes that are the children of the same parent node) also with the same name A. So the example above asks for the oth occurrence of the node with name C which is a child of the nth occurrence of the node with name B which in turn is the child of the mth occurrence of the node with name A.
A known modification in an XPath query is that instead of beginning to walk the document tree from the first node, it is possible to walk it from a reference point, or context node, closer to the desired target node. Whilst this may reduce the extent to which it is luck dictating whether the target node is near the start or end of the relevant portion of the tree, it does not eliminate the issue.
An alternative is to use a relational database. This generally requires setting up database tables, and typically there is quite a degree of processing overhead to run relational data integrity rules, and other software infrastructure necessary for the relational database to operate. This can make extracting the answer to a query slow. Furthermore, relational database software is often produced by a propriety vendor (eg. Oracle™) and may not be readily portable between different users and operating systems.